#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

typedef pair<int, int> PII;

bool myComp(const PII &lhs, const PII &rhs)
{
    return lhs.first <= rhs.first;
}

vector<int> kWayMerge(vector<vector<int> > &input)
{
    priority_queue<PII, vector<PII>, greater<PII> > myQ;
    vector<int> ans;
    vector<int> pos(input.size(), 0);
    for (int i = 0; i < input.size(); i++) {
        if (pos[i] < input[i].size()) {
            myQ.push(make_pair(input[i][0], i));
            pos[i]++;
        }
    }
    while(!myQ.empty()) {
        PII top = myQ.top();
        myQ.pop();
        ans.push_back(top.first);
        if (pos[top.second] < input[top.second].size()) {
            myQ.push(make_pair(input[top.second][pos[top.second]], top.second));
            pos[top.second]++;
        }
    }
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " " ;
    return ans;
}

int main(int argc, char **argv)
{
    vector<vector<int> > input;

    cout << "-----------------Test 1--------------------" << endl;
    vector<int> a;
    for (int i = 0; i < 7; i++) {
        a.clear();
        int size = rand()%10;
        for (int j = 0; j < size; j++) {
            a.push_back(rand()%100);
        }
        sort(a.begin(), a.end());
        input.push_back(a);
        for (int j = 0; j < size; j++)
            cout << a[j] << " ";
        cout << endl;     
    }
    a.clear();
    input.push_back(a);
    kWayMerge(input);
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
